#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 167 两数之和II - 输入有序数组
// 给定一个有序整型数组和一个整数target，在其中寻找两个元素，使其和为target。返回这两个数的索引。
//- 如 numbers = [2, 7, 11, 15], target = 9
//- 返回数字2,7的索引1,2（索引从1开始计算）
// https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

// 时间复杂度： O(n)  空间复杂度：O(1)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        assert(numbers.size() >= 2);
        int l = 0, r = numbers.size() - 1;
        while(l < r) {
            if(numbers[l] + numbers[r] == target) {
                int res[2] = {l + 1, r + 1};
                return vector<int>(res, res + 2);
            }
            else if(numbers[l] +numbers[r] < target)
                l++;
            else
                r--;
        }
        throw invalid_argument("The input has no solution.");
    }
};
int main() {
    int arr[] = {2, 7, 11, 15};
    vector<int> nums(arr, arr + sizeof(arr) / sizeof(int));
    int target = 9;
    vector<int> res = Solution().twoSum(nums, target);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl;
    return 0;
}
